<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
        <head>
                <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
                <title>JavaScript Voronoi</title>
                
                <link rel="stylesheet" href="http://magic-table.googlecode.com/svn/trunk/magic-table/google_visualisation/example.css" type="text/css">
                <!--[if IE]><script type="text/javascript" src="http://javascript-voronoi.googlecode.com/svn/trunk/javascript/excanvas.js"></script><![endif]-->
				<script type="text/javascript" src='http://javascript-voronoi.googlecode.com/svn/trunk/javascript/Voronoi.js'></script>
                <script type="text/javascript" src="http://www.google.com/jsapi"></script>
            
                <script type="text/javascript">
                        
					google.load("visualization", "1");
					google.setOnLoadCallback(setUp);
					var data;
					var voronoi;
					
					function isIE()
				    {
						return /msie/i.test(navigator.userAgent) && !/opera/i.test(navigator.userAgent);
				    }
			
					function setUp()
					{
						var numPoints = 100;
						var tooltipStrings = [];
						data = new google.visualization.DataTable();
				        data.addColumn('number', 'Age');
				        data.addColumn('number', 'Weight');
				        data.addRows(numPoints);
						
						for (var i = 0; i < numPoints; i++) 
						{
							var randomX = Math.floor(Math.random() * (numPoints + 1));
							var randomY = Math.floor(Math.random() * (numPoints + 1));
							
							data.setValue(i, 0, randomX);
							data.setValue(i, 1, randomY);
							
							tooltipStrings[i] = "x = " + randomX + ", y = " + randomY;
						}
		
						voronoi = new greg.ross.visualisation.Voronoi(document.getElementById("voronoiDiv"));
						
						// Don't fill polygons in IE. It's too slow.
						var fillPly = !isIE();
						
						var colours = ['#A7D30C', '#019F62', 'rgba(1,159,98,0)'];
						voronoi.draw(data, {xPos: 50, yPos: 0, width: 500, height: 500, colourGradient: colours, fillPolygons: fillPly, tooltips: tooltipStrings});
					}
					
					function addRandomPoint()
					{
						var numPoints = data.getNumberOfRows() + 1;
						var p = new greg.ross.visualisation.Vertex(Math.random() * (numPoints + 1), Math.random() * (numPoints + 1), 1);
						
						voronoi.addNewPoint(p);
					}
						
                </script>
                
        </head>
        <body>
        <div class="g-unit" id="gc-pagecontent">
        <h1 class="page_title">Visualization: JavaScript Voronoi</h1>

        <div class="toc">
            <ol>
                <li><a href="#Overview">Overview</a>
                <li><a href="#Example">Example</a>
                <li><a href="#Loading">Loading</a>
                <li><a href="#Data_Format">Data Format</a>
                <li><a href="#Configuration_Options">Configuration Options</a>
                <li><a href="#Methods">Methods</a>

                <li><a href="#Events">Events</a>
                <li><a href="#Data_Policy">Data Policy</a>
            </ol>
        </div>

        <h1><a name="Overview" id="Overview"></a>Overview</h1>
        <p>
        This is a JavaScript implementation of an incremental algorithm for a planar ordinary Voronoi diagram.
		The algorithm uses a quaternary tree for spatial indexing to enhance performance and facilitate efficient nearest neighbor searches.
		<br><br>
		An incremental algorithm was chosen over Fortune's sweepline solution so that new points can be inserted 
		into the diagram without needing to regenerate the whole tessellation. The use of the quaternary tree also 
		reduces the average time complexity to <span style="font-weight:bold;">O(n)</span>.
		<br><br>
		Tested in Chrome, Firefox, Opera, Safari and Internet Explorer 6. <span style="font-weight:bold;">Works in IE via use of excanvas.</span>

		<h2>Features</h2>
		<p>
			<ol>
	          <li>
	            <span style="font-weight:bold;">fast</span> incremental algorithm: potentially faster than Fortune's 
	          </li>
	          <li>
	            add points without entire redraw 
	          </li>
			  <li>
	            <span style="font-weight:bold;">pure JavaScript</span> implementation. <span style="font-weight:bold;">No need for Flash.</span>
	          </li>
			  <li>
	            supports <span style="font-weight:bold;">tooltips</span> over Voronoi regions 
	          </li>
			  <li>
	            customisable <span style="font-weight:bold;">colour gradients</span>
	          </li>
			  <li>
	            works in all popular browsers 
	          </li>
	        </ol>
		</p>
		
		<h2>Applications</h2>
		<p>
			<ol>
	          <li>
	            spatial distributions, e.g. animal territories, bird nesting patterns 
	          </li>
	          <li>
	            nearest neighbor search 
	          </li>
			  <li>
	            terrain modelling 
	          </li>
			  <li>
	            robot path planning 
	          </li>
			  <li>
	            Delaunay Triangulation and mesh generation 
	          </li>
	        </ol>
		</p>
        </p>
		<br><br>
        <p>
            This project is hosted by Google-code. Click <a href="http://code.google.com/p/javascript-voronoi/">here</a> to go to the homepage and see
            additional examples and documentation.
        </p>
        <p>
        
        <span style="color:#4466aa">By: Greg Ross</span>

        </p>
        <h1><a name="Overview" id="Overview"></a>Download</h1>
        <p>
            Download the library from the project <a href="http://code.google.com/p/javascript-voronoi/">home page</a>.
        </p>    

        <h1><a name="Example" id="Example"></a>Example</h1>

        <br>
        <div id="voronoiDiv"><!-- voronoi goes here... --></div>
		<input type="button" value="add random point" onclick="addRandomPoint();" />
        <br>
        <br>
        <span class='bodyText'>The above example demonstrates the JavaScript Voronoi tessellation. 
		This is generated by the code shown below. The code creates a set of random points that determine the
		Voronoi regions.</span>
        <br>
        <br>
        <span class='bodyText'>The following code demonstrates basic usage of the API. To see more possibilities, click
        <a href="http://code.google.com/p/javascript-voronoi/">here</a>.</span>
        <br>
        <br>

        <pre class="prettyprint">
&lt;html&gt;
  &lt;head&gt;
	&lt;meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" /&gt;
	
	&lt;!--[if IE]&gt;&lt;script type="text/javascript" 
	  src="http://javascript-voronoi.googlecode.com/svn/trunk/javascript/excanvas.js"&gt;&lt;/script&gt;
	  &lt;![endif]--&gt;
	  
	&lt;script type="text/javascript" 
	  src='http://javascript-voronoi.googlecode.com/svn/trunk/javascript/Voronoi.js'&gt;&lt;/script&gt;
	  
	&lt;script type="text/javascript" src="http://www.google.com/jsapi"&gt;&lt;/script&gt;
		
	&lt;title&gt;Voronoi test stub&lt;/title&gt;
		
  &lt;/head&gt;
  &lt;body&gt;
		
	&lt;script type='text/javascript'&gt;
			
	  google.load("visualization", "1");
	  google.setOnLoadCallback(setUp);
		
	  function setUp()
	  {
	      	var numPoints = 100;
	        var tooltipStrings = [];
	        var data = new google.visualization.DataTable();
	        data.addColumn('number', 'Age');
	        data.addColumn('number', 'Weight');
	        data.addRows(numPoints);
			
	        for (var i = 0; i &lt; numPoints; i++) 
	        {
	          var randomX = Math.floor(Math.random() * (numPoints + 1));
	          var randomY = Math.floor(Math.random() * (numPoints + 1));
				
	          data.setValue(i, 0, randomX);
	          data.setValue(i, 1, randomY);
				
	          tooltipStrings[i] = "x = " + randomX + ", y = " + randomY;
	        }
	
	        voronoi = new greg.ross.visualisation.Voronoi(document.getElementById("voronoiDiv"));
			
	        var colours = ['#A7D30C', '#019F62', 'rgba(1,159,98,0)'];
			
	        voronoi.draw(data, {xPos: 50, yPos: 50, width: 500, height: 500, 
			  colourGradient: colours, fillPolygons: true, tooltips: tooltipStrings});
	  }
		
      &lt;/script&gt;

      &lt;div id='voronoiDiv'&gt;
      &lt;!-- Voronoi goes here... --&gt;
      &lt;/div&gt;
	
  &lt;/body&gt;
&lt;/html&gt;        	
        </pre>

        <h1><a name="Loading" id="Loading"></a>Loading</h1>

        <p>
        A <code>google.load</code> package name is not required.
        </p>

        <pre class="prettyprint">
google.load("visualization", "1");
        </pre>
        
        <p>
            The visualization's class name is <code>greg.ross.visualisation.Voronoi</code>
        </p>
        
        <pre class="prettyprint">
var voronoi = new greg.ross.visualisation.Voronoi(document.getElementById("voronoiDiv"));
        </pre>
        
        <h1><a name="Data_Format" id="Data_Format"></a>Data Format</h1>
        
        <br>
        Two columns are required and both must be numeric. The values in the first column are used for the X-axis and those in the second column are
		 for the Y-axis. 
        
		A tooltip for each point must be specified in a separate array. See the section on options, below, for details.
        
        <h1><a name="Configuration_Options" id="Configuration_Options"></a>Configuration Options</h1>
        
        <br>
        <table>
          <tr>
            <th>Name</th>
            <th>Type</th>
            <th>Default</th>
            <th>Description</th>
          </tr>
		  <tr>
            <td>xPos</td>
            <td>number</td>
            <td>0</td>
            <td>The x-position of the view, relative to the containing element.
            </td>
          </tr>
          <tr>
            <td>yPos</td>
            <td>number</td>
            <td>0</td>
            <td>The y-position of the view, relative to the containing element.
            </td>
          </tr>
          <tr>
            <td>width</td>
            <td>number</td>
            <td>none</td>
            <td>The width of the view.
            </td>
          </tr>
          <tr>
            <td>height</td>
            <td>number</td>
            <td>none</td>
            <td>The height of the view.
            </td>
          </tr>
		  <tr>
            <td>colourGradient</td>
            <td>Colour array</td>
            <td>none</td>
            <td>Should contain three colours. These determine the radial gradient that is applied to Voronoi regions.
            </td>
          </tr>
          <tr>
            <td>fillPolygons</td>
            <td>boolean</td>
            <td>true</td>
            <td>Determines whether the Voronoi regions are gradient-filled with the colours specified above.
			<span style="font-weight:bold;">This should be set to false when the target browser is IE because
			it significantly reduces the rendering speed.</span>
            </td>
          </tr>
          <tr>
            <td>tooltips</td>
            <td>String array</td>
            <td>none</td>
            <td>This is an array of strings corresponding to the points in the view.
			The tooltip for a particular point is displayed when the mouse is moved into its
			Voronoi region.</td>
          </tr>
        </table>
        
        <h1><a name="Methods" id="Methods"></a>Methods</h1>
        
        <br>
        <table>
          <tr>
            <th>Method</th>
            <th>Return Type</th>
            <th>Description</th>
          </tr>
        
          <tr>
            <td><code>draw(data, options)</code></td>
            <td>none</td>
            <td>Draws the view.</td>
          </tr>
          <tr>
            <td><code>addNewPoint(p)</code></td>
            <td>none</td>
            <td>Adds a new point into the diagram without having to recalculate the complete tessellation.</td>
          </tr>
        </table>  
        
        <h1><a name="Events" id="Events"></a>Events</h1>
        
        <p>No triggered events. 
        </p>
        
        <h1><a name="Data_Policy" id="Data_Policy"></a>Data Policy</h1>
        
        <p>
        All code and data are processed and rendered in the browser. No data is sent to any server.
                <br>
                <br>
                <br>
        </p>

      </div>
          
        </body>
</html>
